package com.sicheng.蓝桥.国赛准备.第十三届JavaB;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/18 9:29
 */
public class C左移右移 {
    /**
     * 【问题描述】
     * 小蓝有一个长度为 N 的数组，初始时从左到右依次是 1, 2, 3, . . . N。
     * 之后小蓝对这个数组进行了 M 次操作，每次操作可能是以下 2 种之一：
     * 1. 左移 x，即把 x 移动到最左边。
     * 2. 右移 x，即把 x 移动到最右边。
     * 请你回答经过 M 次操作之后，数组从左到右每个数是多少？
     * 【输入格式】
     * 第一行包含 2 个整数，N 和 M。
     * 以下 M 行每行一个操作，其中 “L x”表示左移 x，“R x”表示右移 x。
     * 【输出格式】
     * 输出 N 个数，代表操作后的数组。
     * 【样例输入】
     * 5 3
     * L 3
     * L 2
     * R 1
     * 【样例输出】
     * 2 3 4 5 1
     * 【样例说明】
     * 样例中的数组变化如下：
     * 试题 C: 左移右移 4
     * 第十三届蓝桥杯大赛软件赛决赛 Java 大学 B 组
     * [1, 2, 3, 4, 5] → [3, 1, 2, 4, 5] → [2, 3, 1, 4, 5] → [2, 3, 4, 5, 1]
     * 【评测用例规模与约定】
     * 对于 50% 的评测用例，1 ≤ N, M ≤ 10000.
     * 对于 100% 的评测用例，1 ≤ N, M ≤ 200000, 1 ≤ x ≤ N.
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        cache = new HashMap<>();
        list = new LinkedList();
        for (int i = 1; i <= n; i++) {
            Node node = new Node(i);
            cache.put(i, node);
            list.addRight(node);
        }

        for (int i = 0; i < m; i++) {
            String s = scanner.next();
            int x = scanner.nextInt();
            Node node = cache.get(x);
            list.remove(node);
            if (s.equals("L")) {
                list.addLeft(node);
            } else {
                list.addRight(node);
            }
        }

        list.list();

    }

    static Map<Integer, Node> cache;
    static LinkedList list;


    static class Node {
        Node pre;
        Node next;
        int data;

        public Node(int data) {
            this.data = data;
        }
    }

    static class LinkedList {

        public LinkedList() {
            this.head = new Node(-1);
            this.tail = new Node(-2);
            head.next = tail;
            tail.pre = head;
        }

        Node head;
        Node tail;

        void addLeft(Node node) {
            head.next.pre = node;
            node.next = head.next;
            node.pre = head;
            head.next = node;
        }

        void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.next = null;
            node.pre = null;
        }

        void addRight(Node node) {
            node.next = tail;
            node.pre = tail.pre;
            tail.pre.next = node;
            tail.pre = node;
        }

        void list() {
            Node t = head.next;
            while (t != tail) {
                System.out.print(t.data + " ");
                t = t.next;
            }
        }
    }
}
